1. Field of the Invention
The present invention relates to computer implementable decision support systems for determining a production plan of feasible production starts such that the plan is consistent with discrete lot-sizing rules, production constraints, and operational objectives. General methodologies within this field of study include optimization and heuristic based algorithms, constraint based programming, and simulation.
2. Background Description
Semiconductor manufacturing involves a range of activities including everything from growing silicon crystals, the source of silicon wafers upon which integrated circuits are grown, to the actual placement and soldering of finished modules to a printed circuit board. Initially raw wafers, cut from a silicon ingot, are processed through a specific sequence of work centers. The end goal of this process is to build a set of devices (integrated circuits) on the surface of the silicon wafer according to a specified circuit design. At a high level, this process includes repeatedly applying four basic steps: deposition, photolithography, etching, and ion implantation. These steps are the means by which materials with specific dielectric properties (e.g. conductors, insulators) are patterned on the surface of the wafer according to precise design specifications. These steps are repeated many times to build up a sequence of layers, where initial layers correspond to the building of circuit components (e.g. transistors) and subsequent layers correspond to metal interconnections between components. Once devices have been built on a wafer they are tested and their properties are recorded for later reference. Wafers are then diced and sorted into individual devices, and subsequently bonded to a substrate and packaged to assemble a module. These modules, which are further tested to determine electromagnetic and thermal characteristics, are eventually assembled onto printed circuit boards to make cards. Finally, cards are tested and those that pass inspection are eventually used in the assembly of a wide range of finished electronic products (e.g. PCs, Printers, CD Players). From the point of view of semiconductor manufacturing, the modules and cards are, by and large, the finished products taken to market.
A Bill-of-material (BOM) is the source of data that specifies components used in the assembly of each particular part number (PN) produced within the manufacturing system. The BOM gives a graphical representation of the dependencies between assemblies and their components. A simple BOM for the wafer, device, and module stages is illustrated in FIG. 1. Once the circuit design is complete the finished wafer, W, is tested. Devices may have a range of quality attributes, denoted by different PNs, D1, D2 and D3 in FIG. 1. For example, testing may reveal some devices operate at a prime frequency, some at a fast frequency, and some at a low frequency (e.g. 50%, 20%, 30% respectively). This aspect of semiconductor manufacturing is referred to as binning. In FIG. 1 further processing is carried out to build module PNs M1, M2 and M3 which are eventually assembled into cards C1, C2 and C3. The material flows in FIG. 1 are based on starting with 100 units of finished wafer. For example, assembly M1 is produced from component D1 with a yield of 90%. Thus, the 50 devices can be used to build 45 modules. Another attribute of the semiconductor manufacturing problems is material substitution. For example, in FIG. 1 the arcs from M1 to M2 and M2 to M3 denote potential substitutions, such as prime modules for fast modules.
A fundamental problem faced in all manufacturing industries is the matching of demand and assets over time. Production lead times necessitate the advance planning of production so that production throughout the production system are coordinated with the end customers demand for any of a wide range of finished products (typically on the order of thousands in semiconductor manufacturing). Such advance planning depends on the availability of finite resources which include: finished goods inventory, work in process (WIP) at various stages of the manufacturing system, and work-center capacity. Furthermore, for a particular job there may be multiple locations, processes, and work centers that could be utilized. Planning and scheduling functions within the semiconductor manufacturing industry can be categorized in various ways. Sullivan and Fordyce (1990) describe a tier system in which each tier is defined by the time frame to which the decisions pertain. Their taxonomy of planning and scheduling decisions is a hierarchical one in which decisions in higher tiers (longer range decisions) affect lower tiers (shorter range decisions).
Short range scheduling involves disaggregating daily targets for production starts into a detailed work-center level schedule that considers lot-sizing constraints. These constraints specify allowable quantities of a production start. For instance, a diffusion furnace may take a batch of at most 100 wafers at a time. Thus an example of a lot-sizing rule would be to always fully load the diffusion furnace each time it is utilized to build a particular PN. This translates to a lot-sizing constraint that daily production starts must be in integer multiples of 100 wafers. In general there may be many such constraints at various points within a multi-stage manufacturing system due to work-center design, container sizes, or yield considerations.
Decisions in higher tiers compute aggregate production plans (e.g. at a daily or weekly granularity) which are subsequently disaggregated in lower tiers to compute detailed short term schedules. Traditionally, higher tier planning systems do not consider lot-sizing rules and therefore result in inefficiency when lower tiers execute these production plans. For example, consider the simplified case in which only two PNs are produced, and each has a lot-sizing rule requiring that they are produced in batches of 100. Further, assume that the firm only has available work-center capacity to build 100 parts per day, however, the higher tier planning system does not consider this constraint when computing a production plan. Therefore, if demand for the two PNs, PN1 and PN2, was 20 and 80 respectively on a particular day, and assuming cycle time is zero, then the higher tier planning system would specify production starts of 20 units for PN1 and 80 units for PN2. Upon receipt of this plan the lower tier scheduling system would be forced to start 100 units of one of the PNs and zero of the other on the specified date, resulting in unanticipated late production of one of the required PNs. However, if the higher tier planning system considered the lot-sizing constraints, it could have anticipated this situation and planned to start a second lot of 100 in advance of the date it is required, and thus utilize work-center capacity (if available) at an earlier time. This simple example illustrates one of the underlying problems with production planning systems that do not consider lot-sizing constraints.